/**
 * @author zowie
 * @param {number} x
 * @return {boolean}
 */

function ULL(n, m) {
  if (n < m) c = 0;
  else if (n == m || m == 0) c = 1;
  else {
    c = 1;
    n = n - m + 1;
    for (i = 1; i <= m; i++) {
      c *= n++;
      c /= i;
    }
  }
  return c;
}
function expand(expr) {
  var result = []
  //extract the a 、b、n and symbol x
  let n = Number(expr.split('^')[1]),
    left = expr.split('^')[0],
    method = left.replace(/[^-+]/g, '')[1] ? left.replace(/[^-+]/g, '')[1] : left.replace(/[^-+]/g, '')[0],
    sym = left.replace(/[^a-z]/g, '');
  if (n == 0) return '1'
  if (left[1] == sym) {
    var a = 1, b = Number(method + left.split(method)[1].replace(')', ''))
  } else {
    if (left[1] == '-') {
      var a = left.replace('(', '==').replace(sym, '==').split('==')[1], b = Number(method + left.replace('(', '').replace(')', '').split(method).pop())
    }
    else {
      let ab = left.replace('(', '').replace(')', '').replace(sym, '').split(method)
      var a = Number(ab[0]), b = Number(method + ab[1])
    }
    if (a == '-') a = -1
  }
  console.log(a, b, n);
  // generator the expansion
  for (let i = 0; i <= n; i++) {
    let u = ULL(n, i), j = Math.pow(a, n - i), k = Math.pow(b, i), temp = u * j * k
    // console.log(temp);
    if (temp == 0) continue
    if (i < n - 1) { //x指数大于1
      if (temp != 1 && temp != -1) {
        temp = temp + sym + '^' + (n - i)
      } else if (temp == 1) { //x指数大于1，但是系数为1
        temp = sym + '^' + (n - i)
      } else {
        temp = '-' + sym + '^' + (n - i)
      }
    } else if (i == (n - 1)) { //x指数为1
      if (temp != 1 && temp != -1) {
        temp = temp + sym
      } else if (temp == 1) { //x指数为1，系数为1
        temp = sym
      } else {//x指数为1，系数为-1
        temp = '-' + sym
      }
    } else { //x的指数为0
      temp = temp
    }
    result.push(temp);
  }
  result = result.join('+').split('+-').join('-')
  return result
}


function expand(expr) {
  let [f, a, x, b, n] = /^\((-?\d*)(.)([-+]\d+)\)\^(\d+)$/.exec(expr);
  a = !a ? 1 : a === '-' ? -1 : +a;
  b = +b;
  n = +n;
  f = Math.pow(a, n);
  if (!n) {
    return '1';
  } else if (!a) {
    return String(Math.pow(b, n));
  } else if (!b) {
    return f + x + (n > 1 ? '^' + n : '');
  } else {
    let result = '';
    for (let i = 0; i <= n; ++i) {
      if (f > 0 && i) result += '+';
      if (f < 0) result += '-';
      if (i || f * f > 1) result += Math.abs(f);
      if (i < n) result += x;
      if (i < n - 1) result += '^' + (n - i);
      f = f * (n - i) * b / a / (i + 1);
    }
    return result;
  }
}

function expand(expr) {

  const memoize = (f) => { const cache = []; return z => cache[z] ? cache[z] : cache[z] = f(z); }

  const factorial = memoize(z => z <= 1 ? 1 : z * factorial(z - 1));

  const factor = (pow, idx) => factorial(pow) / factorial(idx) / factorial(pow - idx);

  const [_, a, x, b, n] = /^\((-?\d+)(.)\+?(-?\d+)\)\^(\d+)$/.exec(expr.replace(/(?<!\d)([^\d\(\)+-^])/, '1$1'))

  return '_'.repeat(+n + 1).split('')
    .map((el, i) => `+${factor(n, i) * a ** (n - i) * b ** i}${x}^${n - i}`)
    .join('')                                           // make primary string 
    .replace(/^\+|\+(?=-)/g, '')                        // remove leading '+' and '+' followed by '-'
    .replace(new RegExp(`${x}\\^0`), '')                // x^0 => _
    .replace(new RegExp(`(${x})\\^1(?!\\d)`), '$1')     // x^1 => x
    .replace(new RegExp(`(?<!\\d)1(?=${x})`, 'g'), '')  // 1x => x
    .replace(new RegExp(`[+-]0${x}?`, 'g'), '');        // 0x^n, 0x, 0 => _
}

function f(n) {
  return n < 2 ? 1 : n * f(n - 1)
}

function expand(expr) {
  return expr.replace(/^\((-?\d*)([a-z])([+-]\d+)\)\^(\d+)$/, function (_, a, b, c, d) {
    if (a == "-")    // -x --> -1x
      a = -1
    if (!a)          // x --> 1x
      a = 1
    if (d == "0")    // ^0 --> 1
      return "1"
    let s = Array.from({ length: +d + 1 }, function (_, i) {
      let first = Math.pow(+a, +d - i) * Math.pow(+c, i) * (f(+d) / f(i) / f(+d - i))
      if (!first)    // 0t --> ""
        return ""
      let expo = +d - i
      return `${first}${i == +d ? "" : b}${expo < 2 ? "" : "^"}${expo < 2 ? "" : expo}` // ^1 or ^0 --> ""
    }).join`+`
    return s.replace(/\+(\-|\+)/g, x => x[1]) // +- --> -
      .replace(/^(-?)(1)([a-z])/g, (_, x, y, z) => x + z) // -1x --> -x or 1x --> x
      .replace(/\+$/g, "") // ++ --> ""
  })
}


console.log(expand("(-i-11)^2"));

